package com.mamingchao.issue.binaryTree;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 二叉树上 有Node o1和 Node o2, 返回o1 和 o2的最近公共祖先
 * 4、给定两个二叉树的节点node1和node2,找到他们的最低公共祖先节点
 * Created by mamingchao on 2024/7/19.
 */
public class LAC {


    // 实现方式一

    public Node method1(Node head, Node o1, Node o2) {
        HashMap<Node, Node> nodeParentMapping = new HashMap<>();
        process1(head, nodeParentMapping);

        HashSet<Node> o1Parents = new HashSet<>();

        head = o1;
        while (head != null) {

            head = nodeParentMapping.get(head);
            o1Parents.add(head);
        }


        head = o2;
        while (head != null) {

            if (o1Parents.contains(head)) {
                return head;
            }

            head = nodeParentMapping.get(head);

        }

        return null;
    }

    private void process1(Node head, HashMap<Node, Node> nodeParentMapping) {
        // base case
        // 到达叶子节点下一层的时候，还是向上 return
        if (head == null) {
            return;
        }
        if (head.leftChild != null) {
            nodeParentMapping.put(head.leftChild, head);
        }
        process1(head.leftChild, nodeParentMapping);
        if (head.leftChild != null) {
            nodeParentMapping.put(head.leftChild, head);
        }
        process1(head.rightChild, nodeParentMapping);


    }

    // 实现方式二
    private Node process2(Node head, Node o1, Node o2) {

        // base case;
        // 如果没有发现 o1 或者o2 ，就直接返回空；
        // 发现了 o1或者 o2, 就直接向上 return o1或者 o2
        if (head == null || head == o1 || head == o2) {
            return head;
        }

        Node left = process2(head.leftChild, o1, o2);
        Node right = process2(head.rightChild, o1, o2);

        if (left != null && right != null) {
            return head;
        }

        return left != null ? left : right;

    }


    // 定义二叉树Node 节点对应的对象
    private class Node {
        private Node leftChild;
        private Node rightChild;

        Node(Node left, Node right) {
            leftChild = left;
            rightChild = right;
        }
    }


}
